//1.递归
/*
🧠 为什么递归能解决这个问题？
每个递归调用都在回答一个问题： “在我这棵子树里，有没有 p 或 q？”

然后把答案往上传。如果左右子树都说“我找到了”，那你站的这个节点就是它们的交汇点。

这就像你在树的每个分叉口都问：“你左边有没有人？你右边有没有人？” 如果两边都说“有”，你就知道你是他们的最近交汇点。
*/
class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        // 终止条件：空节点 或 找到目标节点
        if (!root || root == p || root == q) return root;

        // 递归左右子树
        TreeNode* left = lowestCommonAncestor(root->left, p, q);
        TreeNode* right = lowestCommonAncestor(root->right, p, q);

        // 如果左右都找到了 → 当前节点是最近公共祖先
        if (left && right) return root;

        // 否则返回非空的那个（说明两个节点都在同一边）
        return left ? left : right;
    }
};

//2.存储父节点